package com.Leetcode;

public class LongestDupSubstring {

	public static void main(String[] args) {
		String s = "";
		System.out.println(longestDupSubstring(s));
	}
	public static String longestDupSubstring(String s) {
		int ans = 0,index = 0,count;
		for (int i = 1; i < s.length(); i++) {
			for (int j = 0; j < s.length() - i && i + ans <= s.length(); j += ++count) {
				count = 0;
				while( i + j + count < s.length() && s.charAt(i + j + count) == s.charAt(j + count))
					count++;
				if(ans < count) {
					index = i + j;
					ans = count;
					
				}
			}
		}
		return s.substring(index,index + ans);
    }
}
